"""
目标：给定列表进行归并排序
示例：sequence=[12,27,46,16,25,37,22,29,15,47,48,34]
"""


def merge_sort(array, left, right):
    mid = (left + right) // 2
    if mid < right:
        merge_sort(array, left, mid)
        merge_sort(array, mid + 1, right)
    result = []
    i = left
    j = mid + 1
    while i <= mid and j <= right:
        if array[i] <= array[j]:
            result.append(array[i])
            i += 1
        else:
            result.append(array[j])
            j += 1
    while i <= mid:
        result.append(array[i])
        i += 1
    while j <= right:
        result.append(array[j])
        j += 1
    array[left : right + 1] = result


def MergeSortC(array):
    n = len(array) - 1
    merge_sort(array, 0, n)


def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result


def MergeSortPy(array):
    n = len(array)
    if n < 2:
        return array
    mid = n // 2
    left, right = array[0:mid], array[mid:]
    return merge(MergeSortPy(left), MergeSortPy(right))


from copy import deepcopy

sequence = [12, 27, 46, 16, 25, 37, 22, 29, 15, 47, 48, 34]
sequence2 = deepcopy(sequence)
print(sequence)
MergeSortC(sequence)
print(sequence)
print(sequence2)
print(MergeSortPy(sequence2))
